import functools


class Solution(object):
    def numRollsToTarget(self, n, k, target):
        base = 10 ** 9 + 7

        @functools.cache
        def search(n, target):
            if target > n * k or target <= 0:
                return 0
            if n == 1:
                return 1
            t = 0
            for i in range(1, k + 1):
                t += search(n - 1, target - i)
                t = t % base
            return t

        return search(n, target)
